package top.mysql.SQL2;


/**
 *
 *          索引的底层结构 和 索引的分类
 *
 */
public class IndexesStructure {

/**
 *
 *     --------------------------------2-3树-----------------------------------
 *     一棵完全平衡的2-3树具有以下性质：
 *     1.任意空链接到根结点的路径长度都是相等的。
 *     2. 4-结点变换为3-结点时，树的高度不会发生变化，只有当根结点是临时的4-结点，分解根结点时，树高+1。
 *     3. 2-3树与普通二叉查找树最大的区别在于，普通的二叉查找树是自顶向下生长，而2-3树是自底向上生长。
 *
 *      --------------------------------B树-----------------------------------
 *      本质上是对2-3树的扩展
 *      B树中允许一个结点中包含多个key,具体数量需要看具体的实现。
 *
 *      选择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：
 *      每个结点最多有M-1个key，并且以升序排列；
 *      每个结点最多能有M个子结点；
 *      根结点至少有两个子结点；
 *
 *      --------------------------------B+树-----------------------------------
 *      B+树是对B树的一种变形树，它与B树的差异在于：
 *      1. 非叶结点仅具有索引作用，也就是说，非叶子结点只存储key，不存储value；
 *      2. 树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据。
 *
 *
 *      --------------------------------B+树和B树的对比-----------------------------------
 *      B+ 树的优点在于：
 *      1.由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key。
 *      2.B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，
 *      所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。(即叶子结点是排序好的，且相连构成链表)
 *
 *      B树的优点在于：
 *      由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到
 *      value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶
 *      子结点的深度，才能找到value。(B+树索引的地方为需要查找的数据，还需要继续查找，B树不用)
 *
 *
 *      --------------------------------B+树在数据库中的应用-----------------------------------
 *      在数据库的操作中，查询操作最频繁的一种操作，在设计数据库时，考虑到查询的效率问题，
 *      很多数据库中用到了B+树来提高查询的效率；
 *
 *      区间查询
 *      执行 select * from user where id>=12 and id<=18,如果有了索引，由于B+树的叶子结点形成了一个有序链表，
 *      所以我们只需要找到id为12的叶子结点，按照遍历链表的方式顺序往后查即可，效率非常高。
 *
 *
 *      MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点
 *      的链表指针，就形成了带有顺序指针的B+Tree(双向循环链表)提高区间访问的性能，利于排序。
 *
 *
 *      --------------------------------Hash索引-----------------------------------
 *
 *      哈希索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中。
 *
 *      如果两个(或多个)键值，映射到一个相同的槽位上，他们就产生了hash冲突（也称为hash碰撞），可以通过链表来解决。
 *
 *      特点
 *      A. Hash索引只能用于对等比较(=，in)，不支持范围查询（between，>，< ，...）
 *      B. 无法利用索引完成排序操作
 *      C. 查询效率高，通常(不存在hash冲突的情况)只需要一次检索就可以了，效率通常要高于B+tree索引
 *
 *
 *      面试题： 为什么InnoDB存储引擎选择使用B+tree索引结构?
 *      A. 相对于二叉树，层级更少，搜索效率高；
 *      B. 对于B-tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，
 *         要同样保存大量数据，只能增加树的高度，导致性能降低；
 *      C. 相对Hash索引，B+tree支持范围匹配及排序操作；
 *
 *
 *      --------------------------------索引的分类-----------------------------------
 *
 *      从数据结构角度：        树索引     hash索引
 *
 *
 *    从逻辑角度：
 *
 *      分类                  含义                  特点                        关键字
 *
 *    主键索引      针对于表中主键创建的索引           默认自动创建, 只能有一个         PRIMARY
 *
 *    唯一索引      避免同一个表中某数据列中的值重复     可以有多个                    UNIQUE
 *
 *    常规索引      快速定位特定数据                 可以有多个
 *
 *    全文索引      全文索引查找的是文本中的关键词，    可以有多个                     FULLTEXT
 *                而不是比较索引中的值
 *
 *    联合索引
 *
 *      从物理角度：
 *
 *      分类                      含义                      特点
 *
 *      聚集索引     将数据存储与索引放到了一块，索引结构的叶子      必须有,而且只有一个
 *                 节点保存了行数据
 *
 *      二级索引     将数据与索引分开存储，索引结构的叶子节点关       可以存在多个
 *                 联的是对应的主键
 *
 *      聚集索引选取规则:
 *      如果存在主键，主键索引就是聚集索引。
 *      如果不存在主键，将使用第一个唯一（UNIQUE）索引作为聚集索引。
 *      如果表没有主键，或没有合适的唯一索引，则InnoDB会自动生成一个rowid作为隐藏的聚集索引。
 *
 *
 *      聚集索引的叶子节点下挂的是这一行的数据 。
 *      二级索引的叶子节点下挂的是该字段值对应的主键值。
 *
 *      回表查询：
 *      这种先到二级索引中查找数据，找到主键值，然后再到聚集索引中根据主键值，获取数据的方式，就称之为回表查询。
 *
 */

}
